package OptimalAlgorithm.TwoPointTechnique;

import java.util.Arrays;

//给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
//eg:
//输入: nums = [2,2,3,4]
//输出: 3
//解释:有效的组合是:
//2,3,4 (使用第一个 2)
//2,3,4 (使用第二个 2)
//2,2,3
public class TriangleNumber {
    public int triangleNumber(int[] nums) {
        //排序
        Arrays.sort(nums);
        int sum = 0;
        for(int c = nums.length - 1;c >= 2;c--) {
            int left = 0;
            int right = c - 1;
            while (left < right){
                if (nums[left] + nums[right] > nums[c]) {
                    sum += right - left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return sum;
    }
}
